package com.yaoli.ajob;

import java.util.*;

/**
 * Created by will on 2017/4/16.
 */
public class _015_3Sum {
    public static void main(String[] args) {
        _015_3Sum sum = new _015_3Sum();

        int sums [] = {-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        Arrays.sort(sums);

        for (int i = 0; i < sums.length; i++) {
            System.out.print(sums[i]+"\t");
        }
        //sum.threeSum(sums);
    }


    public List<List<Integer>> threeSum2(int[] nums) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> list = null;

        Arrays.sort(nums);

        for(int i = 0 ; i < nums.length - 2; i++){

            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }

            int rest  = 0 - nums[i];

            int left = i + 1;
            int right = nums.length - 1;

            while(left < right){
                if(nums[left]+nums[right] == rest){
                    list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);

                    left++;
                    right--;

                    while(left < right && nums[left] == nums[left - 1]){
                        left++;
                    }

                    while(left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }

                if(nums[left]+nums[right] < rest){
                    left++;
                }
                if(nums[left]+nums[right] > rest){
                    right--;
                }
            }
        }


        return res;
    }











    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();

        if (nums == null || nums.length < 3) {
            return results;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // skip duplicate triples with the same first numebr
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1, right = nums.length - 1;
            int target = -nums[i];

            twoSum(nums, left, right, target, results);
        }

        return results;
    }

    public void twoSum(int[] nums,
                       int left,
                       int right,
                       int target,
                       List<List<Integer>> results) {
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                ArrayList<Integer> triple = new ArrayList<>();
                triple.add(-target);
                triple.add(nums[left]);
                triple.add(nums[right]);
                results.add(triple);

                left++;
                right--;
                // skip duplicate pairs with the same left
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                // skip duplicate pairs with the same right
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
    }

}
